Statistical inference problems arising within signal processing, data mining,and machine learning naturally give rise to hard combinatorial optimizationproblems. These problems become intractable when the dimensionality of the datais large, as is often the case for modern datasets. A popular idea is toconstruct convex relaxations of these combinatorial problems, which can besolved efficiently for large scale datasets. Semidefinite programming (SDP) relaxations are among the most powerfulmethods in this family, and are surprisingly well-suited for a broad range ofproblems where data take the form of matrices or graphs. It has been observedseveral times that, when the `statistical noise' is small enough, SDPrelaxations correctly detect the underlying combinatorial structures. In this paper we develop asymptotic predictions for several `detectionthresholds,' as well as for the estimation error above these thresholds. Westudy some classical SDP relaxations for statistical problems motivated bygraph synchronization and community detection in networks. We map theseoptimization problems to statistical mechanics models with vector spins, anduse non-rigorous techniques from statistical mechanics to characterize thecorresponding phase transitions. Our results clarify the effectiveness of SDPrelaxations in solving high-dimensional statistical problems.
展开▼
